class Solution {
public:
    bool check(vector<int>& ws, int t, int d) {
        int n = ws.size();
        int cnt = 1;
        for (int i = 1, sum = ws[0]; i < n; sum = 0, cnt++) {
            while (i < n && sum + ws[i] <= t) {
                sum += ws[i];
                i++;
            }
        }
        return cnt - 1 <= d;
    }
    int shipWithinDays(vector<int>& ws, int d) {
        int m = 0, sum = 0;
        for (auto& w : ws) {
            m = max(m, w);
            sum += w;
        }
        int l = m, r = sum;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(ws, mid, d)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }
};


